Bias-Variance Tradeoff of Graph Laplacian Regularizer

摘要

This paper presents a bias-variance tradeoff of graph Laplacian regularizer,which is widely used in graph signal processing and semi-supervised learningtasks. The scaling law of the optimal regularization parameter is specified interms of the spectral graph properties and a novel signal-to-noise ratioparameter, which suggests selecting a mediocre regularization parameter isoften suboptimal. The analysis is applied to three applications, includingrandom, band-limited, and multiple-sampled graph signals. Experiments onsynthetic and real-world graphs demonstrate near-optimal performance of theestablished analysis.